#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-20 11:10 上午
# @Author  : yangdy
# @File    : 2020-10-20.143.重排链表
# @Software: PyCharmCE
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        p, a = head, []
        while p:
            a.append(p)
            p = p.next
        i, j, p = 0, len(a)-1, None
        while i <= j:
            a[i].next = a[j]
            a[j].next = None
            if p:
                p.next = a[i]
            p = a[j]
            i, j = i+1, j-1
        # def work(aa, ll):
        #     if not aa or ll <= 0:
        #         return None
        #     aa[0].next = aa[ll-1]
        #     aa[ll-1].next = work(aa[1:ll-1], ll-2)
        #     return aa[0]
        # work(a, len(a))
        return head
